package java学习.第12章_集合框架;

import org.junit.Test;

import java.util.HashMap;

/**
 * ClassName: C_底层Map
 * Package: java学习.第12章_集合框架
 * Description:
 *
 * @Author 张蛟龙
 * @Create 2023/4/1 12:22
 * @Version 1.0
 */
public class C4_底层Map {
    /**
     * HashMap 底层原理
     * 数组+链表 (jdk7及之前)
     *      底层直接创建了长度为16的一位数组Entry[] table
     * 数组+链表+红黑树(jdk 8)
     * //当某一个数组索引位置上的元素以链表形式存储的个数>8 && 且当前数组的长度> 64时，
     *      会将此链表进化成红黑树，当次位置的元素长度小于6时，会退化成链表
     *      底层在put之后创建了长度为16的一位数组Node[] table
     *
     *      每个node节点会存存入时的  hash  key  value next
     *      这个hash会导致，当key改变时，  扩容时不会重新hash计算
     *
     * //红黑树  排序二叉树
     * 三、HashMap的底层实现原理?以jdk7为例说明:
     *  HashMap map = new HashMap():
     *  在实例化以后，底层创建了长度是16的一维数组Entry[] table.
     *  ...可能已经执行过多次put...
     *  map. put(key1, value1):
     *  首先，调用key1所在类的hashCode()计算key1哈希值1，此哈希值经过某种算法计算以后，得到在Entry数组 中的存放位置 哈希值2。
     *  如果此位置上的数据为空，此时的key1-value1 添加成功。---- 情况1
     *  如果此位置上的数据不为空，(意味着此位置上存在一个或多 个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据
     *  的哈希值:
     *          如果key1的哈希值1与已经存在的数据的哈希值1都不相同，此时key1-value1 添加成功。----情况2
     *          如果key1的哈希值1和已经存在的某一个数据(key2-value2) 的哈希值1相同，继续比较:
     *                  调用key1 所在类的equals(key2)
     *                  如果equals()返回faLse:此时key1-value1添加成功。----情况3
     *                  如果equals().返回true: 默认使用value1替换value2。
     *      补充:关于情况2和情况3:此时key1-value1 和原来的数据以链表的方式存储。
     *
     *  在不断的添加过程中，会涉及到扩容问题，默认的扩容方式:
     *      扩容为原来容量的2倍，并将原有的数据复制过来。
     *
     * HashMap的默认特殊值
     * 默认加载因子 0.75// 即 如原来有16个数组  当存了12个（16*0.75）
     *     第13个时要扩容（如果第13个存的地方原来是空的话  不扩容）
     *     扩容后  要重新根据之前保存的哈希  重新把原来的一个一个添加到新的里
     * 他创建数组的大小  必定是2的幂
     *
     * 如果 链表连的长度大于等于8时 但数组的长度<= 64  他会扩容
     * DEFAULT_INITIAL_CAPACITY : HashMap 的默认容量，16
     * DEFAULT_LOAD_FACTOR: HashMap的默认加载因子: 0.75
     * threshold:扩容的临界值，=容量*填充因子: 16 * 0.75 => 12
     * TREEIFY_THRESHOLD: Bucket 中链表长度大于该默认值，转化为红黑树:8
     * MIN_TREEIFY_CAPACITY: 桶中的Node 被树化时最小的hash表容量: 64
     *
     */
    @Test
    public void HashMap的底层实现原理() {

        HashMap map=new HashMap<>();//底层创建了长度为16的一位数组Entry[] table

        // 如果没 直接添加到Entry[] table数组上  若果有 先比较哈希值不一样 链表直接添加
        //比较哈希值一样  在key的equals方法比较之后
        //没相等的 链表连起来   有的话  用新的替换旧的
        map.put(1,5);//根据key的哈希值经过某种运算存入
    }
}
